package argo.hot100;


import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class FindAnagrams {


    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> res = new ArrayList<>();

        if (p.length() > s.length()) {
            return res;
        }

        int left = 0, cur = 0, size = p.length();
        int[] ps_digit = new int[26];
        int[] ss_digit = new int[26];

        while (cur < size) {
            ps_digit[p.charAt(cur) - 'a']++;
            ss_digit[s.charAt(cur) - 'a']++;
            cur++;
        }
        if (Arrays.equals(ps_digit, ss_digit)) {
            res.add(0);
        }
        cur = 0;
        while (cur + size < s.length()) {
            ss_digit[s.charAt(cur) - 'a']--;
            ss_digit[s.charAt(cur + size ) - 'a']++;
            if (Arrays.equals(ps_digit, ss_digit)) {
                res.add(cur+1);
            }
            cur++;
        }
        return res;

    }


    public static void main(String[] args) {
        System.out.println(Arrays.toString(new FindAnagrams().findAnagrams("baa", "aa").toArray()));
        System.out.println(Arrays.toString(new FindAnagrams().findAnagrams("abab", "ab").toArray()));


        System.out.println(Arrays.toString(new FindAnagrams().findAnagrams("cbaebabacd", "abc").toArray()));
    }
}
